/*
 *  BinaryTree.c
 *
 *  Created on: Dec 2, 2011
 *  	Author: sanglei
 * description: 二叉树的实现
 *
 *  附:试用eclipse c/c++,选择自动编译，会提示错误，对初学者很有帮助
 */

#include <stdio.h>
#include <stdlib.h>
#include "headers/binary_tree.h"
#include "headers/stack_link.h"

static Stack stack;


//构建空二叉树
pBtreeNode init_tree(){
	pBtreeNode root=NULL;
	return root;
}

//插入
pBtreeNode insert(pBtreeNode pNode,pBtreeNode node){

	//C语言里，通常用返回值来记录递归的返回
	//下面这段代码之所以不行，是因为，它无法判断具体应该插入到左还是右
	//用链表建立一个完全二叉树，怎么实现？？？

	//	if(pNode == NULL){
	//		pNode = node;
	//	}else if(pNode->left == NULL){
	//		pNode->left = insert(pNode->left,node);
	//	}else if(pNode->right == NULL){
	//		pNode->right = insert(pNode->right,node);
	//	}

	if(pNode == NULL){
		pNode = node;
	}else if(pNode->value > node->value){//如果相等，则不插入
		pNode->left = insert(pNode->left,node);
	}else if(pNode->value < node->value){
		pNode->right = insert(pNode->right,node);
	}

	return pNode;
}

//建立二叉树
pBtreeNode create_tree(){
	int steps[]={10,4,2,1,3,6,9,7,5};//测试数据
	int i = 0;

	pBtreeNode root = init_tree();
	pBtreeNode node;
	for(;i<sizeof(steps)/sizeof(int);i++){
		node = (pBtreeNode)malloc(sizeof(struct BTreeNode));
		node->value = steps[i];
		node->left=node->right=NULL;
		root = insert(root,node);
	}
	return root;
}

//另外一种构建二叉树的方法
void create(pBtreeNode *p){
	int x;
	scanf("%d",&x);
	if(x==0){
		*p = NULL;
	}else{
		*p = (pBtreeNode)malloc(sizeof(struct BTreeNode));
		(*p)->value = x;
		create(&((*p)->left));
		create(&((*p)->right));
	}
}

//递归：前序遍历二叉树
void pre_tree(pBtreeNode node){
	if(node != NULL){
		printf("%d ",node->value);
		pre_tree(node->left);
		pre_tree(node->right);
	}
}

//非递归：前序遍历二叉树
void pre_tree_n(pBtreeNode node){

	pBtreeNode p = node;
	initStack(&stack,sizeof(pBtreeNode));//初始化栈
	push_stack_link(&stack,&node);//先压入根节点

	while(p || !isEmpty_stack_link(&stack)){//p为NULL 或者 栈不为空时执行循环
		if(p){
			printf("%d ",p->value);//输出节点
			push_stack_link(&stack,&p);
			p = p->left;//访问左孩子
		}else{
			pop_stack_link(&stack,&p);
			p = p->right;
		}
	}

	dropStack(&stack);//清空栈
}

//递归中序遍历
void mid_tree(pBtreeNode node){
	if(node!=NULL){
		mid_tree(node->left);
		printf("%d ",node->value);
		mid_tree(node->right);
	}
}

//非递归中序遍历
void mid_tree_n(pBtreeNode node){
	pBtreeNode p = node;
	initStack(&stack,sizeof(pBtreeNode));//初始化栈
	while(p || !isEmpty_stack_link(&stack)){
		if(p){
			push_stack_link(&stack,&p);
			p = p->left;
		}else{
			pop_stack_link(&stack,&p);
			printf("%d ",p->value);
			p = p->right;
		}
	}

	dropStack(&stack);

}



void main_binary_tree(){
	pBtreeNode root = create_tree();

//	pBtreeNode root;
//	create(&root);

	pre_tree(root);
	pre_tree_n(root);

	printf("\n");

	mid_tree(root);
	mid_tree_n(root);
}
